This invention relates generally to communication or power networks and more particularly to a method and apparatus for planning and implementing automatic protection switching in networks.
As is known in the art, a network includes a plurality of processing sites generally referred to as stations or nodes connected by one or more physical and/or logical connections. When the connections establish transmission of a signal in at least one direction between the nodes, the connections are generally referred to as links. Each node typically performs a switching function and one or more additional functions.
The nodes may be coupled together in a variety of different network structures typically referred to as network topologies. For example, network nodes may be coupled in a circular structure, generally referred to as a ring topology. Other topologies such as star topologies and tree topologies are also known.
The transmission of a signal from a first or source node to a second or destination node may involve the transmission of the signal through a plurality of intermediate links and nodes coupled between the source node and the destination node. Such a succession of links and nodes between a source node and a destination node is referred to as a path.
When a link or node in a path fails, communication between a source node and a destination node in that path is disrupted. Thus, to continue communications between the source and destination nodes, an alternate path must be found and the signal being transmitted from the source node to the destination is routed through the alternate path.
A self-healing network refers to a network which automatically restores connections among nodes in the event of a link or node failure in a path from a source node to a destination node. There is a growing trend and reliance on such networks owing to increasing reliance on and use of high-speed communication networks and the requirement that these communication networks be robust in the case of certain failures. Self-healing networks are central not only to applications where failures occur very often, such as military networks under attack, but also in public networks where failures, albeit rare, can be extremely disruptive. Self-healing networks can also be used in power transmission grids to aid in the distribution of power signals in a power network. Thus self-healing networks have use in a wide variety of applications including but not limited to communications networks and power systems networks.
Self-healing networks typically detect and report a failure, establish and connect a restoration path and then return the network to normal communications, not necessarily in that order. Such self-healing characteristics are incorporated, for example, in the Synchronous Optical Network (SONET) protocols.
A network may be represented as a graph which includes nodes representing the network nodes and edges representing bidirectional connections between the nodes. For a network to be capable of having a self-healing feature which leaves all nodes mutually connected even after the failure of a node and/or an edge, a graph representing the network must be either node and/or edge redundant. A node redundant graph is a graph in which the nodes remain mutually connected even after the elimination of any node in the network. Similarly, an edge redundant graph is a graph in which the nodes remain mutually connected even after elimination of any edge in the network. Node or edge redundancy ensures that all nodes remain connected even after the failure of a node or edge, respectively. One problem, however, is that not all self-healing techniques are guaranteed to work over an arbitrary redundant network (i.e. a network having some portions which are node redundant and other portions which are edge redundant). For instance, a technique which performs self-healing locally may not be able to use the redundancy afforded by a more distant part of the network. Node or edge redundancy is thus the minimum topological requirement for a network to perform self-healing which allows all remaining nodes to remain mutually connected after failure of a node or edge.
Self-healing networks can be classified according to the following three criteria: (1) the use of line (or link) rerouting versus path (or end-to-end) rerouting, (2) the use of centralized versus distributed schemes and (3) the use of precomputed versus dynamically computed routes. The criterion of link rerouting versus path rerouting maps to the criterion, common in optimization, of local versus global. The different criteria are not in practice, selected independently of each other for self-healing networks. Because path rerouting is less local in nature than link rerouting, path rerouting schemes are not usually distributed.
Furthermore, since path rerouting tends to require a relatively large amount of computation and covers a relatively large span of a network compared with link rerouting, path rerouting is typically implemented using precomputed routes. Link rerouting, which usually considers only a few hops away from the rerouted link in the network, is better suited to dynamically computed routes and thus may be done in a distributed fashion.
For example, in a bidirectional self-healing ring (SHR), after a link or node failure, traffic that was previously carried along one link is carried around the rest of the ring using a technique generally referred to as loopback.
One problem with this approach, however, is that a limitation may exist with respect to the number of nodes which may be traversed to replace the failed link. If there is a hop limit, for example, link rerouting may not be possible in a network having a ring topology.
One of the most common ways in SONET to restore rapidly network functionality is to combine SHRs and diversity protection (DP), using add-drop multiplexers (ADMs), for automatic protection switching (APS). Systems using One-to-n (1:n) DP have one back up link for n working links. SHRs perform loopback, which may be regarded as a special case of APS. SHR architectures may be classified into unidirectional rings, in which the duplex channel travels over a different path than the forward channel, and bi-directional rings where the forward channel and the duplex channel may travel the same path. Bi-directional rings typically include two or four fibers. Using mechanical ADMs, the restoration time is typically about 50 milliseconds (ms) while path switching typically requires less than 20 ms and loopback switching typically require under 80 ms. DP or SHR architectures typically require about 10 ms to detect and 50 ms to complete the switch.
One problem with the DP and SHRs approaches is that they require built-in excess capacity to handle failures. Moreover such systems may be difficult to upgrade as more nodes are added to the network. A system utilizing one-to-one (1:1) DP requires the most spare capacity, since the spare capacity is the same as the capacity used during normal operation. SHRs may require as much spare capacity as DP, depending upon network traffic patterns.
Furthermore, placing constraints on possible network topologies may result in increased network cost. For example, a ring topology may be used in a particular application to implement APS. The ring topology, however, may not be the most cost effective topology for the application. This results in a relatively expensive network.
It would, therefore, be desirable to provide a system which allows APS over any arbitrary network topology. Such a system can be used with any existing topology, allows relatively inexpensive expansion of existing networks regardless of topology and allows construction of new and relatively inexpensive networks.
One approach to self-healing uses optical switches such as acousto-optical switches. Optical switches allow switching to a backup fiber, in a time delay which is in the order of micro-seconds (xcexcs). For four-fiber bi-directional rings, optical switches and amplifiers have been proposed to act as ADMs. Optical wavelength division multiplex (WDM) ADMs have been proposed to add/drop channels within a fiber rather than add/drop whole fibers. Such WDM ADMs are useful to overcome the limitation in capacity of traditional SONET ADMs. Many optical WDM ADMs have been proposed and demonstrated. Being able to drop channels rather than whole fibers also gives more flexibility in operating SHRs. WDM survivable rings using a single switch central office have been proposed.
Still another class of self-healing networks which reduces the amount of spare capacity needed, involves utilizing real-time spare capacity in either a distributed or a centralized dynamic restoration system. Thus, real-time excess capacity is used to transmit in case of a failure. This class of self-healing schemes commonly relies on digital cross-connect systems (DCSs) which provide greater flexibility than ADMs. However, such schemes utilize real-time spare capacity at the expense of relatively complex and computationally intensive software processing and thus greater time delays.
Yet other approaches attempt to perform optimal routing in centralized circuit switched networks with the goal of preserving spare capacity. While centralized restoration offers improvement in terms of spare capacity utilization over distributed restoration, it requires real-time computation having a complexity which increases with increasing network size. Thus, one problem with a centralized restoration approach is that it is relatively slow, with restoration times reaching minutes.
To overcome the relatively slow restoration times which occur in centralized restoration schemes, dynamic restoration schemes utilizing distributed control or a hybrid of distributed and centralized control are used. The greatest improvements in speed are provided by distributed schemes. A variety of different distributed schemes have been proposed, each of which rely on some variation of a sender-chooser scheme where a sender floods a network with help messages and a chooser selects a restoration path based on reception of those help messages. Other schemes involve a single sender-chooser pair, one sender and multiple choosers, two senders and two choosers, etc . . . . Thus, suffice it to say that a variety of different self-healing schemes each having different advantages, drawbacks and limitations have been used or proposed.
In addition to self-healing features another feature of increasing importance in networks is that of a multicasting and/or an incasting operation. Multicasting refers to transmission of a signal from a source node to a predetermined set of nodes in a network. When the set of nodes corresponds to all of the nodes in the network, the operation is referred to as a broadcast operation. It is desirable to provide networks having a multicasting feature since in many types of networks, it is relatively simple for a node to receive a signal and replicate it for transmission to several other nodes. Incasting refers to transmission of a signal from a set of nodes in a network to a predetermined destination node. The need for the ability to multicast and/or incast tends to occur relatively often in relatively high-bandwidth networks.
For instance, a server may transmit a single video signal to several receivers or a file server may simultaneously back up data stored thereon to several geographically separate locations. Multicasting and/or incasting are relatively easy to perform when the network nodes are connected in a tree topology. In networks which allow duplication of signals at nodes, a link need only carry at most a single copy of a multicast signal. All-optical nodes for instance, allow simple replication by splitting a first received optical signal into a pair of optical signals and thereafter amplifying the pair of optical signals. The SONET standard, for example, includes a multicasting standard.
If a network is provided having a tree topology and an edge failure occurs in a tree originating at some source node S, all the nodes in the tree which were connected to the source node S that are not downstream of that failure are still connected by the same tree. The nodes of the tree which are downstream of the failure, however, are no longer connected owing to the edge failure. Complete functionality is restored to the network by re-connecting to the source node S the nodes that were downstream of the failure.
It would, therefore, be desirable to provide a network having a redundant tree topology in which such re-connection is possible for both link and node failures. It would also be desirable to provide a means for constructing a tree topology on any node or edge redundant network so that failure of a node or edge does not disconnect any node from the network.
As discussed above, self-healing networks use alternate routes in the case of failures. These routes can be pre-computed or dynamically computed. Pre-computed schemes, a.k.a. APS schemes, are typically fast and guarantee the existence of an alternate route. One problem with such schemes, however, is that they may be bandwidth inefficient. Dynamic schemes can be more bandwidth efficient but are typically slower and generally do not guarantee success, i.e. it is possible that no route with sufficient spare capacity can be found. Thus, to guarantee the existence of an alternate route and provide a relatively fast recovery speed, precomputed routes, such as those specified in SONET protocols, should be used.
A self-healing network having a ring topology is referred to as a self-healing ring. One type of self-healing ring (SHR), is provided from so-called dual-fed path protection, as used in SONET Dual-Fed Unidirectional Path Switched Ring (UPSR). Another type of SHR is provided using loopback protection, as used in SONET Bidirectional Line Switched Ring (BLSR).
In a network utilizing dual-fed path protection, the primary and back-up streams traverse two different paths. In the event of a failure, a node switches from listening to the primary stream to listening to the back-up stream, e.g. by using a SONET add-drop multiplexer (ADM).
In a network utilizing loopback protection, on the other hand, a failure leads to looping on either side of the failure, regardless of whether the failure is a node failure or a link failure. The primary stream is redirected in the opposite direction it was originally traversing until it reaches the other side of the failure, where it rejoins its original route. The actual looping most likely occurs at the nodes adjacent to the failure. One problem with this approach, however, is that failure recovery by loopback may cause the stream to traverse the same nodes twice in opposite directions. This characteristic is referred to as backhauling. Backhauling is undesirable since it results in a waste of bandwidth. Backhauling may be eliminated by looping back at points other than the failure location.
There are many performance differences between path protection and loopback protection. Dual-fed path protection is extremely rapid since it simply entails switching from one live stream to another. Loopback protection requires nodes to have more capabilities such as the ability to loop and possibly the means of distinguishing a node failure from a link failure. However, loopback has spare capacity advantages. In the case of a ring under worst case traffic conditions, path protection may require the spare capacity to be nearly equal to the sum of the rates of all the streams in the ring. Using loopback the spare capacity can be shared with backup channels only having active traffic in the event of a failure. In the case of protection against a link or a node failure, the spare capacity, need only be equal to the maximum rate through any link or node. Depending upon the traffic pattern, the spare capacity savings of loopback may be very significant. This is one reason why SONET BLSR systems are typically more bandwidth efficient than UPSR systems. Another reason BLSR systems are typically more bandwidth efficient than UPSR systems is that BLSR systems are bidirectional which typically shortens paths and provides more routing flexibility.
In view of the above problems and limitations of existing self-healing schemes and in accordance with the present invention, it has been recognized that combining the need for self-healing networks with the usefulness and desirability of performing multicasting and/or incasting operations in mesh and other networks leads to the problem of self-healing networks having a logical tree topology. As described herein, a tree topology refers to a topology having no cycles and in which every node has a single incoming directed arc and in which all nodes are connected to a root node.
It would, therefore, be desirable to provide a self-healing network having a topology which allows multicasting and/or incasting to be accomplished in a relatively easy manner. It would also be desirable to provide a technique to generate logical tree topologies for arbitrary redundant networks since it provides compatibility with all existing redundant networks and, when building new networks, requires no special consideration for the network topology other than it satisfies the redundancy required.
Also, in view of the above problems and limitations it has been recognized in accordance with the present invention that APS, whether it be path or loopback, can be performed on arbitrary redundant networks. That is, for any edge or node redundant network which may be represented as a node or an edge redundant graph, there exists a pair of node or edge-disjoint paths between any two nodes in the network. It should be noted, however, that the mere existence of alternate paths does not insure that the paths can actually be used as an alternate path since they may not have sufficient spare capacity. Therefore, knowing that an alternate path exists is only the starting point for designing an APS scheme which must also consider rules for routing and reserving spare capacity to be used in case of failure.
There have been a variety of proposed path rerouting schemes such as SubNetwork Connection Protection (SNCP) and different variants of it. Such schemes typically use some sort of shortest path selection and may not provide guarantees. Furthermore, automatic protection switching over arbitrary redundant networks need not restrict itself to two paths between every pair of nodes, but can instead be performed with trees, which is more bandwidth efficient for multicast traffic.
Previous methods for loopback protection typically have been limited to SHRs and interconnections of SHRs. While there are many schemes which dynamically re-route around a failure, loopback uses pre-computed routes. SHRs are generally inter-connected by one shared node (single-homed), two adjacent shared nodes (dual-homed) or through links with diversity protection (DP). However, rings place topological constraints which may entail higher costs in network layout.
It would, therefore, also be desirable to provide a technique for providing pre-computed or pre-planned protection mechanisms protection over networks having arbitrary redundant topologies. It would also be desirable to provide a technique for performing loopback protection which provides guaranteed fast recovery and which works on redundant networks having arbitrary topologies.
In accordance with the present invention, an apparatus for generating first and second tree topologies for any source node in a network which can be represented as a node redundant graph, such that any node in the graph remains connected to the source node via at least one tree even after the failure of a node includes means for selecting a source node from a plurality of nodes, means for selecting a cycle around the source node, means for assigning first and second source node values to the source node and means for assigning a node value to each of the first plurality of nodes wherein the node value assigned to each node decreases in a first direction around the cycle. The apparatus further includes means for constructing a first and second set of arcs, each of the arcs in the first set connecting an upstream node and a downstream node with the upstream node having a node value which is greater than the node value of the downstream node and each of the arcs in the second set connecting an upstream node and a downstream node with the upstream node having a node value which is less than the node value of the downstream node. With this particular arrangement, an apparatus for generating tree structures on any node redundant network topology so that failure of any single node leaves all remaining nodes in the tree connected is provided. By providing a redundant tree structure, a network having rapid fault recovery is provided. The benefits of such an apparatus are that the apparatus can be utilized in arbitrary node redundant networks. Additionally, the apparatus allows selection of particular edges to be used to form tree topologies and thus the apparatus can generate a large number of tree topologies for a single network. Furthermore, the tree structures provided by the apparatus of the present invention are well suited to broadcasting and/or multicasting and/or incasting operations. In one particular embodiment, the technique of the present invention includes a means for taking into account costs to allow selection of particular tree structures from a plurality of different tree structures. The main cost component of the system may be specified, for example, as network infrastructure topology or network capacity. Other cost components such as computational complexity may also be specified. Depending upon the specified criteria, a preferred pair of redundant tree structures may be selected from a plurality of different redundant tree structures. Thus, it is possible to select sets of redundant trees which optimize predetermined network performance or cost criteria. Moreover the particular tree topologies obtained may be taken into account when generating a network. For example, it is possible to generate unbalanced tree structures having relatively long individual paths. Alternatively balanced tree structures having relatively short paths may be generated.
In accordance with a further aspect of the present invention, an apparatus for generating first and second tree topologies for any source node in a network which can be represented as an edge redundant graph, such that any node in the graph remains connected to the source node via at least one tree even after the failure of any edge in the graph includes means for selecting a source node from a plurality of nodes, means for selecting a cycle around the source node, means for assigning first and second source node values to the source node and each of a first plurality of nodes in the cycle wherein the node values assigned to each node decrease in a first direction around the cycle and increase in a second opposite direction around the cycle. The apparatus further includes means for constructing first and second sets of arcs, each of the arcs in the first set connecting an upstream node and a downstream node with the upstream node in each of the first set of arcs having a node value which is greater than a node value of the downstream node and each of the arcs in the second set connecting an upstream node and a downstream node with the upstream node in each of the second set of arcs having a node value which is less than a node value of the downstream node. With this particular arrangement, a technique for generating tree structures on any edge redundant network topology so that failure of any edge leaves all remaining nodes connected in the tree, is provided. By providing a redundant tree structure, a network having rapid fault recovery is provided. The benefits of such an apparatus are that it can be applied to arbitrary edge redundant networks, that it provides great flexibility in selecting which particular edges can be used to form the trees and that the tree structures yielded are well suited to broadcasting and/or multicasting and/or incasting operations. The main cost component of the system may be specified as network topology or network capacity. In other cases, it may be desirable to specify other cost components such as computational complexity. Depending upon the specified criteria, a preferred one of a plurality of redundant tree structures may be provided.
The techniques of the present invention thus generate pairs of directed trees which are redundant after the failure of a node or of two directed links corresponding to one undirected link. The technique, however, only requires that the network have the characteristic that it is either node redundant or edge redundant. The only currently used approaches which are applicable to any node or edge redundant graphs consider a pair of node-disjoint or edge-disjoint paths for each pair of communicating nodes and do not guarantee trees. The technique of the present invention does not require any limitation with respect to node-disjoint or edge-disjoint paths. Thus, the networks are relatively flexible and can be utilized in a variety of different network applications including internet protocol (IP), frame relay (FR), optical networking (ON), asynchronous transfer mode (ATM) and SONET applications.
In accordance with a still further aspect of the present invention, a method of establishing at least a pair of paths between a source node and a destination node in a node redundant network including a plurality of nodes, includes the steps of (a) selecting a source node, (b) selecting a cycle around the source node, (c) assigning first and second source node values to the source node, (d) assigning a node value to each of a first plurality of nodes in the cycle wherein the node values assigned to each node decrease in a first direction around the cycle, (e) constructing a first set of arcs, each of the arcs connecting an upstream node and a downstream node, the upstream node in each of the arcs having a node value which is greater than the node value of the downstream node and (f) constructing a second set of arcs, each of the arcs connecting an upstream node and a downstream node, the upstream node in each of the arcs having a node value which is less than the node value of the downstream node. With this particular technique, for any node redundant undirected graph, two directed trees can be built, such that eliminating any node of the undirected graph leaves each node in the graph connected by at least one of the two directed trees. To determine if all nodes desired to be connected are connected, the method further includes the steps of determining if the first plurality of nodes in the cycle includes each of the nodes to be connected in the network and in response to the first plurality of nodes in the cycle not including each of the plurality of nodes to be connected then performing the steps of: (1) selecting a first path having a starting node, an ending node and at least one intermediate node wherein the starting node corresponds to one of the first plurality of nodes in the cycle, the ending node corresponds to a second different one of the first plurality of nodes in the cycle having a value less than the value of the starting node and each of the at least one intermediate nodes corresponds to a node not included in the first plurality of nodes in the cycle; and (2) assigning a node value to each of the at least one intermediate nodes wherein the node values assigned to each of the at least one intermediate nodes decrease when traversing the first path in a direction from the starting node to the ending node. With this approach, an arbitrary number of nodes can be included in the process to provide an ordered set of nodes. The path selection process can be repeated until all desired nodes in the network are included. It should be noted that in some applications it may be desirable to not include all possible nodes in the network. Once all desired nodes are included and ordered, a pair of redundant tree topologies can be formed. In one embodiment, the step of assigning a node value to each of the at least one intermediate nodes includes the step of assigning the intermediate node immediately prior to the ending node a value which is greater than the maximum of: (i) the second value of the source node; and (ii) the value of any node included in the cycle which is smaller than the value of the starting node. With this approach, nodes are ordered in a particular manner. Once the nodes are ordered as desired, a first set of arcs can be constructed on the first path. Each of the arcs link an upstream node and a downstream node, the upstream node in each of the arcs having a node value which is greater than an assigned node value of the downstream node. Also a second set of arcs on the first path can be constructed. Each of the arcs connect an upstream node and a downstream node, the upstream node in each of the arcs having a node value which is less than an assigned node value of the downstream node. Once the arcs have been selected, the first and second tree topologies can be selected by selecting first and second sets of arcs along the path between the starting node and the ending node. In the first set of arcs, the value of each of the nodes decreases along the direction of the arc and in the second set of arcs, the value of each of the nodes increases along the direction of the arcs. The source node is assigned two different values. A first one of the values is the largest node value in the network and the second node value is the smallest node value in the network.
In accordance with a still further aspect of the present invention, a method of generating a pair of directed trees from an arbitrary redundant network includes the steps of (a) selecting a source node, (b) selecting a first cycle around the source node, (c) assigning first and second source node values to the source node, (d) assigning first and second node values to each of a first plurality of nodes in the cycle wherein first ones of the first and second node values assigned to each of the first plurality of nodes decrease in value in a first direction around the first cycle and second ones of the first and second node values assigned to each node decrease in value in the first direction around the first cycle and wherein for each node the first node value is greater than the second node value. The method further includes the step of (e) constructing first and second sets of arcs, each of the arcs linking an upstream node and a downstream node in the first cycle. In the first set of arcs, the upstream node has a node value which is greater than a node value of the downstream node and in the second set of arcs, the upstream node has a node value which is less than a node value of the downstream node. With this particular technique, for any edge-redundant graph a pair of directed trees can be generated from an arbitrary edge redundant network, such that eliminating any edge of the undirected graph leaves each node connected by at least one of the pair of directed trees. In one embodiment, the node values are assigned such that the second value of the first node is greater than the first value of the second node. With this step, an advantageous ordering of the nodes to facilitate generation of redundant tree structures is provided.
The techniques of the present invention may be modified to take into account cost functions. Any cost function can be applied to selected cycles and paths. Thus, the cost functions, such as delay minimization, which are usually associated with Steiner trees for multicasting and/or incasting can be taken into account when selecting cycles and paths.
Furthermore, the techniques may be implemented in a distributed fashion for edge redundancy under certain conditions. Since the union of two trees which share a single node is a tree if the shared node is a source in at least one of the trees, the techniques of the present invention can be independently applied to two or more networks which share a node to independently generate redundant tree pairs for each of the two or more networks. First ones of the redundant tree pairs can be joined to form a first composite redundant tree and second ones of the redundant tree pairs can be joined to form a second composite redundant tree.
It should be noted that the techniques of the present invention have applicability to a wide variety of different types of networks. For example, the techniques may be used to generate tree topologies in communications networks, power networks, chemical supply networks and any other type of network including but not limited to a variety of different supply chain networks. Thus the term xe2x80x9cnetworkxe2x80x9d as used herein refers to a collection of assets, switching apparatus and conduits which permit the transmission of resources. Thus, the networks may be used for communications systems, water or chemical distribution systems and distribution systems in general. In one embodiment, the network may be provided as an internet. The resources may be provided as optical signals and electrical signals such as power signals, information signals, etc . . . or alternatively the resources may be provided as solids or fluids such as gas or liquid fluids.
In accordance with a still further aspect of the present invention, a Bidirectional Link Self-healing Network (BLSN) for implementing bi-directional link automatic protection switching (APS) for an arbitrary edge or node redundant network and a technique for implementing APS recovery in response to an edge or node failure in a network is described. The BLSN technique does not require permanent allocation of spare capacity for each connection and allows sharing of capacity among many network connections by allocating capacity for use only in the event of a failure. The described technique operates so that any network which can be represented as a node or an edge redundant graph remains connected after the failure of a node or an edge in the network. The technique of the present allows loopback protection to be performed over node or edge redundant networks having an arbitrary topology. The technique makes use of connected directed subgraphs of the network. Also described are techniques for generating the directed subgraphs on node and edge redundant networks having an arbitrary network topology. With these techniques, a number of advantages are provided including the ability to provide preplanned protection mechanisms which guarantee fast recovery in the presence of single node or link failures and which work on redundant networks having arbitrary topologies. Moreover with the techniques of the present invention, multiple pairs of subgraphs can be provided.
In accordance with a still further aspect of the present invention, an apparatus for implementing bidirectional link automatic protection switching for an arbitrary node or edge redundant network includes: (a) means for representing a network as a graph having N nodes and E edges; (b) means for generating one or more Bi-directional Link Self-healing Network (BLSN) subgraphs; and (c) means for implementing automatic protection switching for an edge or a node failure in response to detection of an edge or a node failure. With this particular arrangement, a technique useful for performing loopback over a network having an arbitrary redundant topology is provided. By representing a redundant network as a redundant graph and generating one or more BLSN subgraphs, a technique for providing automatic protection switching (APS) on redundant networks having arbitrary topologies is provided. Also, by utilizing pre-planned or pre-stored protection mechanisms, the technique provides a network having a relatively rapid recovery characteristic in the event of the failure of a network node or link.
In accordance with the present invention, a method for implementing bi-directional link automatic protection switching for an arbitrary node or edge redundant network includes the steps of (a) representing a network as a graph having N nodes and E edges; (b) generating a set of bidirectional link self-healing network (BLSN) subgraphs; and (c) implementing automatic protection switching for an edge or a node failure in response to detection of an edge or a node failure. With this particular technique, a method for implementing bi-directional link APS for an arbitrary edge or node redundant network is provided. Unlike previous techniques used to generate tree structures, in the present technique, spare capacity is not specifically allocated for each connection. Instead, spare capacity may be shared among many connections and is used only in the event of a failure. For a network with N nodes and full-duplex links with capacity C, the technique provides a plurality of advantageous protection properties in the presence of a single edge or node failure including but not limited to: (1) protection of at least C arbitrary simplex unicast or multicast connections; (2) protection of up to C*N*(Nxe2x88x921)/2 simplex unicast or multicast connections, depending upon network topology and traffic requirements (i.e. source and destinations for each connection); (3) a spare bandwidth requirement bounded only by the maximum traffic routed over a link or through a node (for a node redundant network); (4) requirement of only local information for APS switching; and (5) provision of protection for arbitrary node or edge redundant network topologies.
In accordance with a further aspect of the present invention, a method for generating a directed subgraph from a network which can be represented as an edge redundant graph includes the steps of: (a) selecting a cycle on a subgraph, (b) selecting a direction for the cycle, (c) determining whether some nodes are not yet reached by any path or cycle, (d) in response to some nodes not yet being reached by any path or cycle, choosing a next path or a next cycle, (e) selecting a direction for the path or cycle selected in step (d), (e) repeating steps (c) and (d) until all nodes are reached by a path or cycle and (f) in response to all desired nodes being reached by a path or cycle, defining first and second subgraphs B, R with the second subgraph having the same set of nodes as the first subgraph with arcs in the reversed direction from the arcs in the first subgraph. With this particular arrangement, construction of a pair of directed subgraphs B, R both of which span the desired nodes and both of which can each be used for primary connections between any pair of nodes in the subgraph results in a method which allows loopback in an edge redundant network. In the event of a failure, effected connections on the first subgraph B are looped back around the failure using the second subgraph R. Similarly, effected connections on the second subgraph R are looped back around the failure using the first subgraph B. For instance, if a network G having a ring topology were used, then the first and second subgraphs B and R would correspond to cycles around the ring in the clockwise and counter-clockwise directions, respectively. In the case where an edge between nodes x and y in a edge redundant network having any arbitrary topology fails (i.e. edge [x,y] in the network fails), if arc (x,y) is an arc of subgraph B, and arc (y,x) is an arc of subgraph R, two looping arcs, Bloopx,y and Rloopy,x can be generated so that signals which arrive for transmission on arc (x,y) in subgraph B are now looped back to node x along subgraph R and any signal which arrives for transmission on arc (y,x) in subgraph R is looped back to node y in subgraph B. In this manner, edge [x,y] can be successfully bypassed as long as there exists a working path with sufficient capacity from node x to node y in subgraph R and a working path with sufficient capacity from node y to node x in subgraph B. Each arc includes a first or start node sometimes referred to hereinbelow as a xe2x80x9cheadxe2x80x9d and a second or end node sometimes referred to hereinbelow as a xe2x80x9ctail.xe2x80x9d Signals flow or are transmitted from the start (or head) node to the end (or tail) node. Thus, an arc is an ordered set of nodes between which a signal flows or is transmitted in only one direction. The looping arcs Bloopx,y and Rloopy,x can be generated in the following manner. Looping arc Bloopx,y is generated by attaching the head of arc (x,y) which belongs to the set of arcs in subgraph B to the tail of arc (y,x) which belongs to the set of arcs in subgraph R so that signals which arrive for transmission on arc (x,y) in subgraph B are now looped back to node x in subgraph R. Similarly, looping arc Rloopy,x is generated by attaching the head of arc (y,x) which belongs to the set of arcs in subgraph R to the tail of arc (x,y) at node y which belongs to the set of arcs in subgraph B so that any signal which arrives for transmission on arc (y,x) in subgraph R is looped back to node y in subgraph B.
In accordance with yet another aspect of the present invention, a method for generating a directed subgraph in a network which can be represented as node redundant graph includes the steps of: (a) selecting a first edge from an undirected graph having a first plurality of nodes and a first plurality of edges with each of the edges having a predetermined capacity, (b) selecting a first cycle which includes the first edge, (c) assigning node values to each node in the first cycle in accordance with a predetermined criteria to define a directed subgraph having a second plurality of nodes and a second plurality of arcs, and (d) determining whether the subgraph includes all nodes to be connected. In response to the subgraph not including all nodes to be connected, the method further includes the steps of: (e1) selecting a path having a starting node and an ending node already included in the subgraph but which includes at least one node not already included in the subgraph and (e2) assigning node values to each of the at least one intermediate nodes in the first path in accordance with a predetermined criteria to define a new directed subgraph having a third plurality of nodes and a third plurality of arcs. With this particular technique, a failed network node from the third plurality of nodes can be successfully bypassed to maintain a connection between a source and a destination. In a preferred embodiment, the method further includes the step of repeating steps (d), (e1) and (e2) until all desired nodes are included in a subgraph. With this arrangement, a failed network node included in the subgraphs can be successfully bypassed to maintain a connection between a source node and a destination node. The processing which takes place in the event of a node failure is similar to that performed in response to a link failure except that many links may be affected. In the case where a node n fails, then all nodes which are adjacent to node n perform loopback as above in the edge redundant case. In particular, if arc (x,n) is an arc of subgraph B, and arc (n,x) is an arc of subgraph R, a looping arc Bloopx,n connecting the head of the arc in subgraph B originating at node x to the tail of the arc in subgraph R terminating at node x is generated. If arc (y,n) is an arc of subgraph R, and arc (n,y) is an arc of subgraph B, a looping arc Rloopy,n connecting the head of the arc in subgraph R originating at node y to the tail of the arc in subgraph R terminating at node y is generated. Now, node n can be successfully bypassed as long as there exists a working path with sufficient capacity from node x to y in subgraph R and a working path with sufficient capacity from node y to node x in subgraph B for all nodes x,y such that arcs (x,n), (n,y) belong to the set of arcs in subgraph B. This loopback is more general than the type of loopback used in a ring since the loopback is not restricted to use a backhaul route. Therefore, in order to guarantee loopback in the edge and node redundant cases, subgraphs B and R must be chosen so that in the event of any node or edge failure which affects subgraphs B or R, there exists a working path around the failure on the other graph. In addition, it is necessary to insure sufficient back-up capacity on subgraphs B and R to support the loopback signals in addition to the unaffected connections on subgraphs B and R.
To insure sufficient capacity when protecting against a link failure and representing the maximum arc load in the B and R subgraphs, respectively, as Larc,B and Larc,R, then in the worst case, if a link fails which is carrying Larc,B and Larc,R in subgraphs B and R, respectively, and the loopback paths for this link pass through links carrying Larc,R and Larc,B on subgraphs R and B, respectively, then sufficient capacity exists for loopback provided that Larc,B+Larc,Rxe2x89xa6C, where C is the capacity of a link in each direction.
To insure sufficient capacity in the node redundant case let Lnode,B and Lnode,R be the maximum throughput through a node in the B and R graphs, respectively. The worst case for a node failure is when a node with a load Lnode,B through it in B fails and all these connections are routed through an arc carrying Larc,R in R, or vice-versa. Therefore, for the node case, it is sufficient to have Lnode,B+Larc,Rxe2x89xa6C and similarly Larc,B+Lnode,Rxc2x1C.
It should be noted that the spare capacity requirements for node protection are, in general, higher than those for link protection since the traffic through a node is generally larger than that through a link. However, in the special case of a ring, the required excess capacity to protect against a node failure is no more, and can be less, than that required for an edge failure. The reason for this is that connections destined to or from the failed node do not need to be protected. In particular, Lnode,Bxe2x89xa6Larc,B and Lnode,Rxe2x89xa6Larc,R. So for example, sufficient back-up capacity exists for a node or link failure as long as the maximum load on any link in any direction does not exceed C/2. These constraints can be applied even with different link capacities within the network.
It should also be noted that given a redundant network G there are many possible choices for B which can be chosen to optimize certain criteria, e.g. bandwidth utilization, geographic considerations, political considerations, etc . . . .